/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */

let left;
var isPalindrome = function (head) {
    left = head;
    return traverse(head);
};

var traverse = function (right) {
    if (right == null) return true;
    let res = traverse(right.next);

    // 后序遍历
    res = res && (right.val === left.val);
    left = left.next;
    return res;
}

var isPalindrome = function (head) {
    if (head == null) {
        return false;
    }
    let left = head;
    let midNode = findMid(head);
    let right = reverse(midNode);

    // 开始比较
    while (right != null) {
        if (left.val !== right.val) {
            return false;
        }
        left = left.next;
        right = right.next;
    }

    return true;
};

// 双指针找到链表中间结点
var findMid = function (head) {
    let fast, slow;
    fast = slow = head;
    while (fast != null && fast.next != null && slow != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // slow 现在指向链表中点
    return slow;
}

// 翻转以head为头的链表
var reverse = function (head) {
    let pre = null, cur = head;
    while (cur != null) {
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}
